In order to support high-speed networking systems, access control lists (ACLs) are maintained in content addressable memory (CAM) arrays at network nodes to grant or deny access to incoming packets to the network. Typically, ACLs that are implemented in a CAM array operate on a first match basis. That is, when a packet is subjected to an ACL, the first ACL entry that matches with certain criteria of the incoming packet (i.e., matches a certain packet profile) is used to determine whether access will be granted or denied to the packet. Because network access is determined on a first match basis when an ACL is implemented in a CAM array, the order of ACL entries in the CAM array is important. In particular, populating an ACL in a CAM array must be performed in a manner that maintains the designated order of the ACL entries. Because the designated order of ACL entries must be maintained, populating an ACL often requires that existing ACL entries be rewritten to the CAM array so that new ACL entries are placed in the proper order within the CAM array. Rewriting data in a CAM array is relatively slow when compared to rewriting data in other types of memory (i.e., up to one hundred times slower than rewriting the same data to random access memory (RAM)). Since rewriting data such as ACL entries into a CAM array is relatively slow, when changes need to be made to a CAM-based ACL, rewriting ACL entries may subject traffic to a “rough” or transitional CAM array profile while the ACL entries are being rewritten. This may lead to inaccurate application of ACL rules to incoming traffic.
FIGS. 1A–1C depict an embodiment of a conventional technique for populating an ACL that is stored in a CAM array. FIG. 1A depicts a base ACL that is stored in a CAM array. Entries in the ACL are referred to herein as ACL entries. The ACL entries are identified by the capital letters to the left of the CAM array and a corresponding ACL rule is identified within each ACL entry. An example CAM array address identifier (ID) is identified by the number to the right of each ACL entry.
FIG. 1B depicts a “base ACL” which includes the ACL set W, X, Y, and Z, and a “new ACL” which includes the ACL set W, X, X1, Y, and Z. The base ACL represents an ACL before editing and the new ACL represents the same ACL after it has been modified to include ACL edits. In the example of FIG. 1B, a new ACL entry, X1, is added as a result of ACL editing. The new ACL entry is designated for insertion after ACL entry X and before ACL entry Y. The new ACL reflects the order in which the ACL entries should exist in the CAM array.
A conventional technique for populating CAM arrays with new ACL entries involves rewriting all of the ACL entries to the CAM array in the new order. Rewriting the entire new ACL into the CAM array ensures that the ACL entries are stored in the designated order. Although rewriting the entire ACL into the CAM array ensures that all of the ACL entries are stored in the designated order, rewriting the entire new ACL into the CAM array can, as described above, lead to application of a rough CAM array profile to incoming traffic.
FIG. 1C depicts an example of how the CAM array may be populated with the new ACL set when using a conventional technique. As depicted in FIG. 1C, although entry X1 has been inserted between entries X and Y, all of the ACL entries have been rewritten into the CAM array, as indicated by the CAM array address IDs to the right of the CAM array, which have all changed from those in FIG. 1A. In an alternate embodiment, rather than rewriting every ACL entry in the CAM array, only those ACL entries below the first modified ACL entry are rewritten. A drawback to this alternative is that rewriting only those ACL entries below the first modified ACL entry may still result in the application of rough CAM array profiles, especially if the first change is at the top of the ACL.
In view of the need to minimize the roughness of the CAM array profile, what is needed is a technique for managing an ACL in a CAM array that maintains the proper order of ACL entries while reducing the number of ACL entries that need to be rewritten.